package sword_offer;

/**
 * @author Synhard
 * @version 1.0
 * @Class sword_offer.Code31
 * @Description 在R行C列的矩阵上，我们从(r0, c0)面朝东面开始
 *
 * 这里，网格的西北角位于第一行第一列，网格的东南角位于最后一行最后一列。
 *
 * 现在，我们以顺时针按螺旋状行走，访问此网格中的每个位置。
 *
 * 每当我们移动到网格的边界之外时，我们会继续在网格之外行走（但稍后可能会返回到网格边界）。
 *
 * 最终，我们到过网格的所有R * C个空间。
 *
 * 按照访问顺序返回表示网格位置的坐标列表。
 * 示例 1：
 *
 * 输入：R = 1, C = 4, r0 = 0, c0 = 0
 * 输出：[[0,0],[0,1],[0,2],[0,3]]
 *
 *
 * 示例 2：
 *
 * 输入：R = 5, C = 6, r0 = 1, c0 = 4
 * 输出：[[1,4],[1,5],[2,5],[2,4],[2,3],[1,3],[0,3],[0,4],[0,5],[3,5],
 * [3,4],[3,3],[3,2],[2,2],[1,2],[0,2],[4,5],[4,4],[4,3],[4,2],[4,1],
 * [3,1],[2,1],[1,1],[0,1],[4,0],[3,0],[2,0],[1,0],[0,0]]
 *
 * 提示：
 *
 * 1 <= R <= 100
 * 1 <= C <= 100
 * 0 <= r0 < R
 * 0 <= c0 < C
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-03-19 8:57
 */
public class Code31 {
    public static void main(String[] args) {
        int[][] res = spiralMatrixIII(5, 6, 1, 4);
        System.out.println();
    }
    public static int[][] spiralMatrixIII(int R, int C, int r0, int c0) {
        if (R == 1 && C == 1) {
            return new int[][]{{0, 0}}; // 如果只有一个结点直接返回
        }
        int[][] res = new int[R * C][2];
        int resIndex = 0;
        res[resIndex][0] = r0;
        res[resIndex++][1] = c0;
        int left = c0 - 1, right = c0 + 1, top = r0 - 1, bottom = r0 + 1; // 定义四个边界

        while (true) {
            c0 = right;
            for (int i = r0; i <= bottom; i++) {
                if (i >= 0 && i <= R - 1 && c0 >= 0 && c0 <= C - 1) {
                    if (!(res[resIndex - 1][0] == i && res[resIndex - 1][1] == c0)) {
                        res[resIndex][0] = i;
                        res[resIndex++][1] = c0;
                        if (resIndex == R * C) {
                            return res;
                        }
                    }
                }
                // System.out.println(i + " " + c0);
            }
            right++;
            r0 = bottom;
            for (int i = c0; i >= left; i--) {
                if (r0 >= 0 && r0 <= R - 1 && i >= 0 && i <= C - 1) {
                    if (!(res[resIndex - 1][0] == r0 && res[resIndex - 1][1] == i)) {
                        res[resIndex][0] = r0;
                        res[resIndex++][1] = i;

                        if (resIndex == R * C) {
                            return res;
                        }
                    }
                }
                // System.out.println(r0 + " " + i);
            }
            bottom++;
            c0 = left;
            for (int i = r0; i >= top; i--) {
                if (i >= 0 && i <= R - 1 && c0 >= 0 && c0 <= C - 1) {
                    if (!(res[resIndex - 1][0] == i && res[resIndex - 1][1] == c0)) {
                        res[resIndex][0] = i;
                        res[resIndex++][1] = c0;

                        if (resIndex == R * C) {
                            return res;
                        }
                    }
                }
                // System.out.println(i + " " + c0);
            }
            left--;
            r0 = top;
            for (int i = c0; i <= right; i++) {
                if (r0 >= 0 && r0 <= R - 1 && i >= 0 && i <= C - 1) {
                    if (!(res[resIndex - 1][0] == r0 && res[resIndex - 1][1] == i)) {
                        res[resIndex][0] = r0;
                        res[resIndex++][1] = i;

                        if (resIndex == R * C) {
                            return res;
                        }
                    }
                }
                // System.out.println(r0 + " " + i);
            }
            top--;

        }
    }
}
/*
设置四个边界，四个边界依次扩大，但要注意每次遍历的起点不要和上次的终点重复了
 */